package Algorithm.SearchAlgorithmDome;

import java.util.Scanner;

/**
 * ClassName:BinarySearch001
 * Package:Algorithm.SearchAlgorithmDome
 * Description:
 *
 * @Author:ZhangXin
 * @Create2023/2/3-19:01
 * @Version:v1.0
 */
public class BinarySearch001 {
    /*二分查找---->提高查找效率*/
    /*
     * 前提条件：数组中的数据必须是有序的
     * 核心逻辑：每次排除一半的查找范围
     * min      mid      max
     * mid = (min+max)/2
     * 如果要查找的元素在mid的左边,缩小范围时,min不变,max = mid - 1
     * 如果要查找的元素在mid的右边,缩小范围时,max不变,min = mid + 1
     * {7,23,79,81,103,127,131,147}*/
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
        while (true) {
            System.out.println("请输入要查找的数据：");
            int number = sc.nextInt();
            int index = binarySearch(arr, number);
            if (index >= 0) {
                System.out.println("该数据在数组的" + index + "索引上");
            } else {
                System.out.println("要查找的数据不存在,请重新输入!");
            }
        }

    }

    public static int binarySearch(int[] arr, int number) {
        //定义两个变量,记录要查找的范围
        int min = 0;
        int max = arr.length - 1;

        //利用循环不断去找要查找的数据
        while (true) {
            if (min > max) {
                return -1;
            }
            //找到min和max的中间位置
            int mid = (min + max) / 2;
            //拿着mid指向的元素跟要查找的元素进行比较
            if (arr[mid] > number) {
                //number在mid的左边
                max = mid - 1;
            } else if (arr[mid] < number) {
                //number在mid的右边
                min = mid + 1;
            } else if (arr[mid] == number) {
                return mid;
            }
        }

    }
}
